
struct ListNode
{
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};
// BM9 删除链表的倒数第n个节点
class Solution
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param n int整型
     * @return ListNode类
     */
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        // write code here
        // 找到倒数为n的节点 快慢指针
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto pre = dummy;
        ListNode *slow = head;
        ListNode *fast = head;
        for (int i = 0; i < n; i++)
        {
            fast = fast->next;
        }
        while (fast)
        {
            pre = pre->next;
            slow = slow->next;
            fast = fast->next;
        }
        // 更改节点指向
        pre->next = slow->next;
        slow->next = nullptr;
        return dummy->next;
    }
};